/*
  描述
  给定一个二叉树，确定他是否是一个完全二叉树。
  完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，
  其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。
  （第 h 层可能包含 [1~2h] 个节点）
*/

const isCompleteTree = (root) => {

  const queue = []
  // 如果为空树，则直接返回true
  if (!root) return true
  queue.push(root)
  let flag = false
  while (queue.length) {
    const node = queue.shift()
    // 当第一次遇到node为空时，设置flag为true
    if (!node) {
      flag = true
      continue
    }
    // 后面节点不为空，并且flag已经为true时，直接返回false
    if (flag) return false
    queue.push(node.left)
    queue.push(node.right)
  }
  return true
}
